7.8 写像の演習問題

from 論理と集合から始める数学の基礎読書会

注：$ f^\leftarrow[A]:=\{x\in U|f(x)\subseteq A\}

ただし、$ Uは$ fの定義域とした

7.1 $ U=\{1,2,3,4,5\},f:U\to U;1\mapsto3,2\mapsto5,3\mapsto5,4\mapsto2,5\mapsto3のとき

(1) $ fの値域は

$ f[U]=\{y\in U|\exist x\in U.y=f(x)\}

$ = \{2,3,5\}

(2) 像を求める

$ f[\{2,3,5\}]=\sout{\{5\}}\{3,5\}

そんな聞き方してる？nishio.icon

$ \{2,3,5\} の像って言ってない？

しまったミスったtakker.icon

$ f(2)=f(3)=5だけど、$ f(5)=3でした

(3) 逆像を求める

$ f^\leftarrow[\{3\}]=\{x\in U|f(x)\subseteq\{3\}\}

$ = \{1,5\}

7.2 $ f:U\to V,g:U\to Uのとき、以下を論理式で書き下す

(1) $ fは全射でない

$ \lnot(\forall y\in V\exist x\in U.y=f(x))

$ \iff\exist y\in V\forall x\in U.y\neq f(x)

(2)$ gは恒等写像ではない

$ \lnot(\forall x\in U.x=g(x)

$ \iff\exist x\in U.x\neq g(x)

7.3 $ f:\N\ni x\mapsto\frac12(x+3\llbracket x\%2=1\rrbracket)\in\N($ \llbracket\bullet\rrbracketはIverson Bracket)が全射だが単射で無いことを示す

全射性：

$ \top

$ \iff\forall y\in\N.2y\in\N

$ \iff\forall y\in\N\exist x\in\N.2y=x

$ \iff\forall y\in\N\exist x\in\N.y=\frac12x

$ \implies\forall y\in\N\exist x\in\N.y=f(x)

単射でない：

$ f(3)=\frac12(3+3)=3=\frac12\cdot 6=f(6)だから単射でない

7.4 $ f:\Z\ni x\mapsto 2x\llbracket x>0\rrbracket+(-2x+1)\llbracket x\le0\rrbracket\in\Nが全単射であることを示せ

全射性：

$ \top

$ \iff\forall y\in\N.\frac12y\in\N

$ \iff\forall y\in\N\exist x\in\N.y=2x

$ \implies\forall y\in\N\exist x\in\N.y=f(x)

$ \implies\forall y\in\N\exist x\in\Z.y=f(x)

単射性：

$ \forall x,x'\in\Z.

$ f(x)=f(x')

$ \iff2x\llbracket x>0\rrbracket+(-2x+1)\llbracket x\le0\rrbracket=2x'\llbracket x'>0\rrbracket+(-2x'+1)\llbracket x'\le0\rrbracket

$ \iff\begin{dcases}2x=2x'&\text{if }x>0\land x'>0\\2x=-2x'+1&\text{if }x>0\land x'\le0\\-2x+1=2x'&\text{if }x\le0\land x'>0\\-2x+1=-2x'+1&\text{if }x\le0\land x'\le0\end{dcases}

$ \iff\begin{dcases}2x=-2x'+1&\text{if }x>0\land x'\le0\\-2x+1=2x'&\text{if }x\le0\land x'>0\\x=x'&\text{otherwise}\end{dcases}

$ \iff\begin{dcases}x+x'=\frac12\notin\Z&\text{if }x>0\land x'\le0\\x+x'=\frac12\notin\Z&\text{if }x\le0\land x'>0\\x=x'&\text{otherwise}\end{dcases}

$ \implies\begin{dcases}\bot&\text{if }x>0\land x'\le0\\\bot&\text{if }x\le0\land x'>0\\x=x'&\text{otherwise}\end{dcases}

$ \implies x=x'

$ \therefore\forall x,x'\in\Z.f(x)=f(x')\implies x=x'

7.5 g:\N^2\ni (x,y)\mapsto\frac12(x+y-2)(x+y-1)+y\in\Nが全単射であることを示せ

7.6 $ f:U\to V,A\subseteq U,B\subseteq Vのとき、以下を示せ

これなにげに証明したことなかったので示したいtakker.icon

/miyamonz/写像の像と逆像に関する基本的な定理

(1) $ A\subseteq f^\leftarrow[f[A]]

$ A\subseteq f^\leftarrow[f[A]]

$ \iff \forall x\in A.x\in f^\leftarrow[f[A]]

$ \iff \forall x\in A.f(x)\in f[A]

$ \iff \forall x\in A\exist x'\in A.f(x)=f(x')

$ \underline{\iff\top\quad}_\blacksquare

矢印で考えるとよくわかる

TODO:図を書く

(2) $ (\forall x,x'\in U.f(x)=f(x')\implies x=x')\implies A= f^\leftarrow[f[A]]

$ f^\leftarrow[f[A]]\subseteq A

$ \iff\forall x\in f^\leftarrow[f[A]].x\in A

$ \iff (\forall x\in U.f(x)\in f[A]\implies x\in A)

$ \iff (\forall x\in U.(\exist x'\in A.f(x)=f(x'))\implies x\in A)

なるほど。単射の性質から逆算できそうだtakker.icon

証明

$ \forall x\in U.

$ \exist x'\in A.f(x)=f(x')

$ \implies \exist x'\in A.x=x'

$ \because\forall x,x'\in U.f(x)=f(x')\implies x=x'

$ \implies x\in A

$ \iff(\forall x\in U.(\exist x'\in A.f(x)=f(x'))\implies x\in A

$ \iff f^\leftarrow[f[A]]\subseteq A

$ \iff A= f^\leftarrow[f[A]]

$ \because(1)

(3) $ f[f^\leftarrow[B]]\subseteq B

$ f[f^\leftarrow[B]]\subseteq B

$ \iff\forall y\in f[f^\leftarrow[B]].y\in B

$ \iff(\forall y\in V.(\exist x\in f^\leftarrow[B].y=f(x))\implies y\in B)

$ \iff(\forall y\in V.(\exist x\in U.y=f(x)\in B)\implies y\in B)

$ \iff(\forall y\in V.(\exist x\in U.y=f(x))\land y\in B\implies y\in B)

$ \iff\top

(4) $ (\forall y\in V\exist x\in U.y=f(x))\implies f[f^\leftarrow[B]]= B

$ \forall y\in V\exist x\in U.y=f(x)

$ \implies \forall y\in B\exist x\in U.y=f(x)

$ \iff \forall y\in B\exist x\in U.f(x)\in B\land y=f(x)

$ \iff \forall y\in B\exist x\in f^\leftarrow[B].y=f(x)

$ \iff B\subseteq f[f^\leftarrow[B]]

7.7 $ f:U\to V,g:V\to Wのとき、以下を示せ

(1) $ f,gが単射$ \implies g\circ fは単射

$ \forall x,x'\in U.

$ g(f(x))=g(f(x'))

$ \implies f(x)=f(x')

$ \because gは単射

$ \implies x=x'

$ \because fは単射

$ \therefore g\circ fは単射

(2) $ f,gが全射$ \implies g\circ fは全射

$ f,gが全射

$ \iff\begin{dcases}\forall y\in V\exist x\in U.y=f(x)\\\forall y\in W\exist x\in V.y=g(x)\end{dcases}

$ \implies\forall y\in W\exist y'\in V\exist x\in U.\begin{dcases}y'=f(x)\\y=g(y')\end{dcases}

$ \iff\forall y\in W\exist x\in U.y=g(f(x))

$ \iff g\circ fは全射

(3)$ g\circ fは単射$ \implies fは単射

$ g\circ fは単射

$ \iff\forall x,x'\in U.(g(f(x))=g(f(x'))\implies x=x')

$ \implies\forall x,x'\in U.

$ f(x)=f(x')

$ \implies g(f(x))=g(f(x'))

$ \implies x=x'

$ \implies fは単射

(4)$ g\circ fは全射$ \implies gは全射

$ g\circ fは全射

$ \iff\forall y\in W\exist x\in U.y=g(f(x))

$ \iff\forall y\in W\exist x\in V\exist x'\in U.y=g(x)\land x=f(x')

$ \implies\forall y\in W\exist x\in V.y=g(x)

$ \iff gは全射

図解するとよくわかるので図解したいtakker.icon

図解すると、「$ g\circ f は単射$ \implies \left.g\right|_{f[U]} は単射」という予想が立つ

論理式で書き下すと$ \forall x,x'\in U.(g(f(x))=g(f(x'))\implies x=x')\implies\forall x,x'\in f[U].(g(x)=g(x')\implies x=x') になる

論理式で書き出してみると、図解とはまた別の視点で当たり前な式に見える

これを(3')としておく

証明

$ \forall x,x'\in U.(g(f(x))=g(f(x'))\implies x=x')

$ \implies\forall y,y'\in V.

$ \exist x,x'\in U.y=f(x)\land y'=f(x')\land g(y)=g(y')

$ \implies\exist x,x'\in U.y=f(x)\land y'=f(x')\land g(f(x))=g(f(x'))

$ \implies\exist x,x'\in U.y=f(x)\land y'=f(x')\land x=x'

$ \implies\exist x,x'\in U.y=f(x)=f(x')=y'

$ \implies y=y'

$ \implies\forall y,y'\in V.(y,y'\in f[U]\land g(x)=g(x')\implies x=x')

$ \iff\forall x,x'\in f[U].(g(x)=g(x')\implies x=x')

(4)については、(4')「$ g\circ f は全射$ \implies \left.g\right|_{f[U]} は全射」が成り立つ

(5)$ g\circ fは単射$ \land fは全射$ \implies gは単射

$ g\circ fは単射$ \land fは全射

$ \implies \left.g\right|_{f[U]} は単射$ \land f[U] =V

$ \because(3')

$ \implies \left.g\right|_V は単射

$ \iff gは単射

(6)$ g\circ fは全射$ \land gは単射$ \implies fは全射

2024-03-08 19:28:27 2024-03-05に脳内で図解しようとしたら、よくわからなくなって眠ってしまったtakker.icon

イメージを言葉で表すと

$ gが全単射なので、$ Uから矢印が出ていない$ Vの要素があると全射でなくなり矛盾するということ

うーん、やっぱ図で書いたほうがわかりやすいな……

論理式に変換

$ \begin{dcases}\forall w\in W\exist u\in U.w=g(f(u))\\\forall v,v'\in V.g(v)=g(v')\implies v=v'\end{dcases}\implies\forall v\in V\exist u\in U.v=f(u)

いろいろ代入したらいけそう

証明

$ \begin{dcases}\forall w\in W\exist u\in U.w=g(f(u))\\\forall v,v'\in V.g(v)=g(v')\implies v=v'\end{dcases}

$ \iff\forall v\in V\forall w\in W\exist u\in U\begin{dcases}w=g(f(u))\\\forall v'\in V.g(v)=g(v')\implies v=v'\end{dcases}

$ \implies\forall v\in V\forall w\in W\exist u\in U\begin{dcases}w=g(f(u))\\g(v)=w\implies v=f(u)\end{dcases}

$ \implies\forall v\in V\forall w\in W\exist u\in U.(g(v)=w\implies v=f(u))

$ \implies\forall v\in V\forall w\in W\exist u\in U.v=f(u)

$ \iff\forall v\in V\exist u\in U.v=f(u)

うーん、ごちゃごちゃしてるtakker.icon

$ \exist x\in U.(g(v)=w\implies v=f(u))から$ g(v)=w\impliesを削っているところが冗長

ゆる募: もっとスッキリした証明

もっときれいな証明思いついた！

$ \begin{dcases}\forall w\in W\exist u\in U.w=g(f(u))\\\forall v,v'\in V.g(v)=g(v')\implies v=v'\end{dcases}

$ \implies\begin{dcases}\forall v\in V\exist u\in U.g(v)=g(f(u))\\\forall v,v'\in V.g(v)=g(v')\implies v=v'\end{dcases}

$ vを導入したあと、$ wに$ g(v)を代入した

$ \iff\forall v\in V\exist u\in U\begin{dcases}g(v)=g(f(u))\\\forall v',v''\in V.g(v')=g(v'')\implies v'=v''\end{dcases}

量化子の位置移動 & 束縛変数のリネーム

$ \implies\forall v\in V\exist u\in U\begin{dcases}g(v)=g(f(u))\\g(v)=g(f(u))\implies v=f(u)\end{dcases}

$ v'に$ vを、$ v''に$ f(u)を代入した

$ \implies\forall v\in V\exist u\in U.v=f(u)

nishio.icon

$ f:U\to V,g:V\to Wのとき、以下を示せ

$ g\circ fは全射$ \land gは単射$ \implies fは全射

対偶を示す: $ fは全射でない $ \implies ($ g\circ fは全射$ \land gは単射)でない

もし$ f が全射でないならある要素$ a があって $ a\notin f[U]

$ gは単射であるとき$ b := g(a)について$ b := g(x)となる$ x\in V は$ aだけ

$ a \notin f[U] なので$ g(f(x)) = b となる$ x \in U は存在しない、よって$ g\circ fは全射でない Q.E.D.

/emoji/tada.icontakker.icon

修正✅

$ a \notin V

ここ「ある要素$ a があって$ a\notin f[U] 」かな？takker.icon

「ある要素$ aがあって$ a \notin V」だと$ \exist a.a\notin Vだから、任意の場合で成立してしまう

そうだnishio.icon

7.8 $ \exist U\neq\varnothing\exist V\neq\varnothing\exist f:U\to V\exist g:V\to U.g\circ f={\rm id}_U\land f\circ g\neq{\rm id}_Vが正しいかどうか調べよ

$ {\rm id}_\bulletは全単射だから、7.7より$ gが単射で$ fが全射となる

つまり、7.8は正しくて、その具体例は全射でない単射$ gと単射でない全射$ fの組み合わせで表せる

具体例を1個示せば証明したことになる

証明

$ f:\{1\}\ni n\mapsto n\in\{1,2\}

$ g:\{1,2\}\ni n\mapsto 1\in\{1\}

とすると、以下が成り立つ

$ g\circ f={\rm id}_{\{1\}}

$ \because\forall n\in\{1\}.g(f(n))=g(n)=1=n

$ f\circ g\neq{\rm id}_{\{1,2\}}

$ \because f(g(2))=f(1)=1\neq2

$ \therefore\exist U\neq\varnothing\exist V\neq\varnothing\exist f:U\to V\exist g:V\to U.g\circ f={\rm id}_U\land f\circ g\neq{\rm id}_V

巻末の答え見たら、まったく同じ構成方法だったtakker.icon

まあ一番単純なのはこれくらいしかないよね

7.9 空でない集合$ Uについて、$ f\circ f={\rm id}_Uを満たす$ f:U\to Uを$ U上の対合変換と呼ぶ

対合律を満たす写像のことtakker.icon

(1) $ S=\{1,2,3,4,5,6\},g:S\to S;1\mapsto1,2\mapsto4,6\mapsto3で$ gが対合変換のとき、$ g(3),g(4),g(5)を求めよ

$ 2=g^2(2)=g(4)

$ 6=g^2(6)=g(3)

これで$ 5以外は写す先が決まったので、自動的に$ 5=g(5)だとわかる

(2)$ \forall U\forall f: U\to Uにて$ fが対合変換なら$ fが全単射であることを示せ

$ \forall U\forall f:U\to U.

$ \forall u,u'\in U.

$ f(u)=f(u')

$ \implies f(f(u))=f(f(u'))

$ \implies u=u'

$ \because対合変換

$ \therefore fは単射

$ \forall U\forall f:U\to U.

$ \top

$ \implies\forall u\in U. u=f(f(u))

$ \because対合変換

$ \implies\forall u\in U\exist u'\in U.u=f(u')

$ \because f(u)\in U

$ \implies fは全射

以上より、$ fは全単射である

(3)$ \forall U\forall f: U\to Uにて$ fが対合変換なら$ f=f^{-1}であることを示せ

$ fは全単射

$ \implies f\circ f^{-1}={\rm id}_U

$ \implies f\circ f\circ f^{-1}=f\circ{\rm id}_U=f

$ \iff{\rm id}_U\circ f^{-1}=f

$ \because fは対合変換

$ \underline{\iff f^{-1}=f\quad}_\blacksquare